package com.peng.leetcode.tree;

/**
 * SortedArrayToBST
 *
 * @author: lupeng6
 * @create: 2020/12/25 21:08
 */
public class SortedArrayToBST {

    public static void main(String[] args) {
        int[] array = {-10,-3,0,5,9};
        TreeNode root = sortedArrayToBST(array);
        System.out.println(TreeMain.inOrder(root));
    }

    public static TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length <= 0) {
            return null;
        }
        return generate(nums, 0, nums.length - 1);
    }

    public static TreeNode generate(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        int middle = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[middle]);
        root.left = generate(nums, left, middle - 1);
        root.right = generate(nums, middle + 1, right);
        return root;
    }
}
